package hard;

import java.util.Arrays;
import java.util.Comparator;

/**
 * 给你一个二维整数数组 envelopes ，其中 envelopes[i] = [wi, hi] ，表示第 i 个信封的宽度和高度。
 *
 * 当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。
 *
 * 请计算 最多能有多少个 信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。
 *
 * 注意：不允许旋转信封。
 *
 * 链接：https://leetcode.cn/problems/russian-doll-envelopes
 * @author 胡宇轩
 * @Email: programboy@163.com
 */
public class RussianDollEnvelopes {
    /**
     * 这道题的思路比较巧妙
     * 先按照宽度进行升序排序，如果宽度相同的，则按照其长度降序排序.最后按照高度找到最长递增子序列的长度即可
     * 比如：[[5,4],[6,4],[6,7],[2,3]] 排序后：[[2,3],[5,4],[6,7],[6,4]]
     * 参考：https://leetcode.cn/problems/russian-doll-envelopes/solution/zui-chang-di-zeng-zi-xu-lie-kuo-zhan-dao-er-wei-er/
     *
     * */
    class Solution {
        public int maxEnvelopes(int[][] envelopes) {
            Arrays.sort(envelopes, (o1, o2) -> o1[0] == o2[0] ? o2[1] - o1[1] : o1[0] - o2[0]);
            int[] incrementalArr = new int[envelopes.length];
            int lastIndex = 0;
            incrementalArr[lastIndex] = envelopes[0][1];
            for (int i = 0; i < envelopes.length; i++) {
                if (envelopes[i][1] > incrementalArr[lastIndex]) {
                    incrementalArr[++lastIndex] = envelopes[i][1];
                } else {
                    int index = binarySearch(incrementalArr, lastIndex, envelopes[i][1]);
                    incrementalArr[index] = envelopes[i][1];
                }
            }
            return lastIndex + 1;
        }

        public int binarySearch (int[] nums,int lastIndex, int value){
            int start = 0;
            int end = lastIndex;
            // ！！！ 注意这里要用<= 因为我们需要找到右边界
            while (start <= end) {
                int mid = (start + end) / 2;
                if(nums[mid] == value) {
                    return mid;
                } else if (nums[mid] < value) {
                    start = mid + 1;
                } else {
                    end = mid - 1;
                }
            }
            return start;
        }
    }
}
